{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Nodes With the Highest Score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #array #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #数组 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countHighestScoreNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计最高分的节点数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵根节点为 <code>0</code> 的&nbsp;<strong>二叉树</strong>&nbsp;，它总共有 <code>n</code>&nbsp;个节点，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;。同时给你一个下标从&nbsp;<strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>parents</code>&nbsp;表示这棵树，其中&nbsp;<code>parents[i]</code>&nbsp;是节点 <code>i</code>&nbsp;的父节点。由于节点 <code>0</code>&nbsp;是根，所以&nbsp;<code>parents[0] == -1</code>&nbsp;。</p>\n",
    "\n",
    "<p>一个子树的 <strong>大小</strong>&nbsp;为这个子树内节点的数目。每个节点都有一个与之关联的&nbsp;<strong>分数</strong>&nbsp;。求出某个节点分数的方法是，将这个节点和与它相连的边全部 <strong>删除</strong>&nbsp;，剩余部分是若干个 <strong>非空</strong>&nbsp;子树，这个节点的 <strong>分数</strong>&nbsp;为所有这些子树 <strong>大小的乘积</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回有 <strong>最高得分</strong>&nbsp;节点的 <strong>数目</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<p><img alt=\"example-1\" src=\"https://assets.leetcode.com/uploads/2021/10/03/example-1.png\" style=\"width: 604px; height: 266px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>parents = [-1,2,0,2,0]\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>\n",
    "- 节点 0 的分数为：3 * 1 = 3\n",
    "- 节点 1 的分数为：4 = 4\n",
    "- 节点 2 的分数为：1 * 1 * 2 = 2\n",
    "- 节点 3 的分数为：4 = 4\n",
    "- 节点 4 的分数为：4 = 4\n",
    "最高得分为 4 ，有三个节点得分为 4 （分别是节点 1，3 和 4 ）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"example-2\" src=\"https://assets.leetcode.com/uploads/2021/10/03/example-2.png\" style=\"width: 95px; height: 143px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>parents = [-1,2,0]\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "- 节点 0 的分数为：2 = 2\n",
    "- 节点 1 的分数为：2 = 2\n",
    "- 节点 2 的分数为：1 * 1 = 1\n",
    "最高分数为 2 ，有两个节点分数为 2 （分别为节点 0 和 1 ）。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == parents.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>parents[0] == -1</code></li>\n",
    "\t<li>对于&nbsp;<code>i != 0</code>&nbsp;，有&nbsp;<code>0 &lt;= parents[i] &lt;= n - 1</code></li>\n",
    "\t<li><code>parents</code>&nbsp;表示一棵二叉树。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-nodes-with-the-highest-score](https://leetcode.cn/problems/count-nodes-with-the-highest-score/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-nodes-with-the-highest-score](https://leetcode.cn/problems/count-nodes-with-the-highest-score/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,2,0,2,0]', '[-1,2,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "      n = len(parents)\n",
    "      nodeNum = [1 for _ in range(n)]\n",
    "      child = [[] for _ in range(n)]\n",
    "      indegree = [0] * n\n",
    "      score = collections.defaultdict(int)\n",
    "      for i in range(1, n):  \n",
    "        indegree[parents[i]] += 1\n",
    "        child[parents[i]].append(i)\n",
    "      leaf = []\n",
    "      for i in range(1, n):\n",
    "        if indegree[i] == 0:  leaf.append(i)\n",
    "      \n",
    "      while leaf:\n",
    "        nex = []\n",
    "        for cur in leaf:\n",
    "          cnt = max(1, n - nodeNum[cur])\n",
    "          for children in child[cur]:\n",
    "            cnt *= nodeNum[children]\n",
    "          score[cnt] += 1\n",
    "          if cur:\n",
    "            indegree[parents[cur]] -= 1\n",
    "            nodeNum[parents[cur]] += nodeNum[cur]\n",
    "            if indegree[parents[cur]] == 0: nex.append(parents[cur])\n",
    "        leaf = nex\n",
    "      \n",
    "      return score[max(score.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "      n = len(parents)\n",
    "      nodeNum = [1 for _ in range(n)]\n",
    "      child = [[] for _ in range(n)]\n",
    "      indegree = [0] * n\n",
    "      score = collections.defaultdict(int)\n",
    "      for i in range(1, n):  \n",
    "        indegree[parents[i]] += 1\n",
    "        child[parents[i]].append(i)\n",
    "      leaf = []\n",
    "      for i in range(1, n):\n",
    "        if indegree[i] == 0:  leaf.append(i)\n",
    "      \n",
    "      while leaf:\n",
    "        nex = []\n",
    "        for cur in leaf:\n",
    "          cnt = max(1, n - nodeNum[cur])\n",
    "          for children in child[cur]:\n",
    "            cnt *= nodeNum[children]\n",
    "          score[cnt] += 1\n",
    "          if cur:\n",
    "            indegree[parents[cur]] -= 1\n",
    "            nodeNum[parents[cur]] += nodeNum[cur]\n",
    "            if indegree[parents[cur]] == 0: nex.append(parents[cur])\n",
    "        leaf = nex\n",
    "      \n",
    "      return score[max(score.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "      n = len(parents)\n",
    "      nodeNum = [1 for _ in range(n)]\n",
    "      child = [[] for _ in range(n)]\n",
    "      indegree = [0] * n\n",
    "      score = collections.defaultdict(int)\n",
    "      for i in range(1, n):  \n",
    "        indegree[parents[i]] += 1\n",
    "        child[parents[i]].append(i)\n",
    "      leaf = []\n",
    "      for i in range(1, n):\n",
    "        if indegree[i] == 0:  leaf.append(i)\n",
    "      \n",
    "      while leaf:\n",
    "        nex = []\n",
    "        for cur in leaf:\n",
    "          cnt = max(1, n - nodeNum[cur])\n",
    "          for children in child[cur]:\n",
    "            cnt *= nodeNum[children]\n",
    "          score[cnt] += 1\n",
    "          if cur:\n",
    "            indegree[parents[cur]] -= 1\n",
    "            nodeNum[parents[cur]] += nodeNum[cur]\n",
    "            if indegree[parents[cur]] == 0: nex.append(parents[cur])\n",
    "        leaf = nex\n",
    "      \n",
    "      return score[max(score.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "      n = len(parents)\n",
    "      nodeNum = [1 for _ in range(n)]\n",
    "      child = [[] for _ in range(n)]\n",
    "      indegree = [0] * n\n",
    "      score = collections.defaultdict(int)\n",
    "      for i in range(1, n):  \n",
    "        indegree[parents[i]] += 1\n",
    "        child[parents[i]].append(i)\n",
    "      leaf = []\n",
    "      for i in range(1, n):\n",
    "        if indegree[i] == 0:  leaf.append(i)\n",
    "      \n",
    "      while leaf:\n",
    "        nex = []\n",
    "        for cur in leaf:\n",
    "          cnt = max(1, n - nodeNum[cur])\n",
    "          for children in child[cur]:\n",
    "            cnt *= nodeNum[children]\n",
    "          score[cnt] += 1\n",
    "          if cur:\n",
    "            indegree[parents[cur]] -= 1\n",
    "            nodeNum[parents[cur]] += nodeNum[cur]\n",
    "            if indegree[parents[cur]] == 0: nex.append(parents[cur])\n",
    "        leaf = nex\n",
    "      \n",
    "      return score[max(score.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        \n",
    "        dct =[[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            dct[parents[i]].append(i)\n",
    "        ans = [0]*n\n",
    "        sub  =[0]*n\n",
    "        stack = [[0, -1]]\n",
    "        while stack:\n",
    "            i, fa = stack.pop()\n",
    "            if i >= 0:\n",
    "                stack.append([~i, fa])\n",
    "                for j in dct[i]:\n",
    "                    stack.append([j, i])\n",
    "            else:\n",
    "                i = ~i\n",
    "                lst = [sub[j] for j in dct[i]]\n",
    "                s = sum(lst) + 1\n",
    "                lst.append(n-s)\n",
    "                cur = 1\n",
    "                for w in lst:\n",
    "                    if w:\n",
    "                        cur *= w\n",
    "                ans[i] = cur\n",
    "                sub[i] = s\n",
    "        return ans.count(max(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        childrens = [[]for _ in range(n)]\n",
    "        degree = [0] * n\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                continue\n",
    "            childrens[p].append(i)\n",
    "            degree[p] += 1\n",
    "        visited = set()\n",
    "        size = [1] * n\n",
    "        queue = collections.deque()\n",
    "        for i in range(n):\n",
    "            if degree[i] == 0:\n",
    "                visited.add(i)\n",
    "                continue\n",
    "            Flag = True\n",
    "            for j in childrens[i]:\n",
    "                if degree[j] != 0:\n",
    "                    Flag = False\n",
    "            if Flag:\n",
    "                queue.append(i)\n",
    "\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for children in childrens[cur]:\n",
    "                size[cur] += size[children]\n",
    "            degree[cur] = 0\n",
    "            visited.add(cur)\n",
    "            p = parents[cur]\n",
    "            if p not in visited and p != -1:\n",
    "                Flag = True\n",
    "                for children in childrens[p]:\n",
    "                    if degree[children] != 0:\n",
    "                        Flag = False\n",
    "                if Flag:\n",
    "                    queue.append(p)\n",
    "        \n",
    "        ans = 1\n",
    "        max_point = 0\n",
    "        for i in range(n):\n",
    "            temp = 1\n",
    "            for children in childrens[i]:\n",
    "                temp *= size[children]\n",
    "            if parents[i] != -1:\n",
    "                # cur = i\n",
    "                # while parents[cur] != -1:\n",
    "                #     cur = parents[cur]\n",
    "                # temp *= (size[cur] - size[i])\n",
    "                temp *= (size[0] - size[i])\n",
    "            if temp > max_point:\n",
    "                max_point = temp\n",
    "                ans = 1\n",
    "            elif temp == max_point:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        childrens = [[]for _ in range(n)]\n",
    "        degree = [0] * n\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                continue\n",
    "            childrens[p].append(i)\n",
    "            degree[p] += 1\n",
    "        visited = set()\n",
    "        size = [1] * n\n",
    "        queue = collections.deque()\n",
    "        for i in range(n):\n",
    "            if degree[i] == 0:\n",
    "                visited.add(i)\n",
    "                continue\n",
    "            Flag = True\n",
    "            for j in childrens[i]:\n",
    "                if degree[j] != 0:\n",
    "                    Flag = False\n",
    "            if Flag:\n",
    "                queue.append(i)\n",
    "\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for children in childrens[cur]:\n",
    "                size[cur] += size[children]\n",
    "            degree[cur] = 0\n",
    "            visited.add(cur)\n",
    "            p = parents[cur]\n",
    "            if p not in visited and p != -1:\n",
    "                Flag = True\n",
    "                for children in childrens[p]:\n",
    "                    if degree[children] != 0:\n",
    "                        Flag = False\n",
    "                if Flag:\n",
    "                    queue.append(p)\n",
    "        \n",
    "        ans = 1\n",
    "        max_point = 0\n",
    "        for i in range(n):\n",
    "            temp = 1\n",
    "            for children in childrens[i]:\n",
    "                temp *= size[children]\n",
    "            if parents[i] != -1:\n",
    "                # cur = i\n",
    "                # while parents[cur] != -1:\n",
    "                #     cur = parents[cur]\n",
    "                # temp *= (size[cur] - size[i])\n",
    "                temp *= (size[0] - size[i])\n",
    "            if temp > max_point:\n",
    "                max_point = temp\n",
    "                ans = 1\n",
    "            elif temp == max_point:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        childrens = [[]for _ in range(n)]\n",
    "        degree = [0] * n\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                continue\n",
    "            childrens[p].append(i)\n",
    "            degree[p] += 1\n",
    "        visited = set()\n",
    "        size = [1] * n\n",
    "        queue = collections.deque()\n",
    "        \n",
    "        # 先找叶子结点的上一个结点\n",
    "        for i in range(n):\n",
    "            if degree[i] == 0:\n",
    "                visited.add(i)\n",
    "                continue\n",
    "            Flag = True\n",
    "            for j in childrens[i]:\n",
    "                if degree[j] != 0:\n",
    "                    Flag = False\n",
    "            if Flag:\n",
    "                queue.append(i)\n",
    "\n",
    "        # 把所有子树的size都求出来\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for children in childrens[cur]:\n",
    "                size[cur] += size[children]\n",
    "            degree[cur] = 0\n",
    "            visited.add(cur)\n",
    "            p = parents[cur]\n",
    "            if p not in visited and p != -1:\n",
    "                Flag = True\n",
    "                for children in childrens[p]:\n",
    "                    if degree[children] != 0:\n",
    "                        Flag = False\n",
    "                if Flag:\n",
    "                    queue.append(p)\n",
    "        \n",
    "        # 找答案\n",
    "        ans = 1\n",
    "        max_point = 0\n",
    "        for i in range(n):\n",
    "            temp = 1\n",
    "            for children in childrens[i]:\n",
    "                temp *= size[children]\n",
    "            if parents[i] != -1:\n",
    "                # cur = i\n",
    "                # while parents[cur] != -1:\n",
    "                #     cur = parents[cur]\n",
    "                # temp *= (size[cur] - size[i])\n",
    "                temp *= (size[0] - size[i])\n",
    "            if temp > max_point:\n",
    "                max_point = temp\n",
    "                ans = 1\n",
    "            elif temp == max_point:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        childrens = [[]for _ in range(n)]\n",
    "        degree = [0] * n\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                continue\n",
    "            childrens[p].append(i)\n",
    "            degree[p] += 1\n",
    "        visited = set()\n",
    "        size = [1] * n\n",
    "        queue = collections.deque()\n",
    "        for i in range(n):\n",
    "            if degree[i] == 0:\n",
    "                visited.add(i)\n",
    "                continue\n",
    "            Flag = True\n",
    "            for j in childrens[i]:\n",
    "                if degree[j] != 0:\n",
    "                    Flag = False\n",
    "            if Flag:\n",
    "                queue.append(i)\n",
    "\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for children in childrens[cur]:\n",
    "                size[cur] += size[children]\n",
    "            degree[cur] = 0\n",
    "            visited.add(cur)\n",
    "            p = parents[cur]\n",
    "            if p not in visited and p != -1:\n",
    "                Flag = True\n",
    "                for children in childrens[p]:\n",
    "                    if degree[children] != 0:\n",
    "                        Flag = False\n",
    "                if Flag:\n",
    "                    queue.append(p)\n",
    "        \n",
    "        ans = 1\n",
    "        max_point = 0\n",
    "        for i in range(n):\n",
    "            temp = 1\n",
    "            for children in childrens[i]:\n",
    "                temp *= size[children]\n",
    "            if parents[i] != -1:\n",
    "                # cur = i\n",
    "                # while parents[cur] != -1:\n",
    "                #     cur = parents[cur]\n",
    "                # temp *= (size[cur] - size[i])\n",
    "                temp *= (size[0] - size[i])\n",
    "            if temp > max_point:\n",
    "                max_point = temp\n",
    "                ans = 1\n",
    "            elif temp == max_point:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        # 拓扑排序\n",
    "        # 记录当前节点的子树个数，从叶节点往上推\n",
    "        n = len(parents)\n",
    "        edges = defaultdict(list)\n",
    "        edges2 = defaultdict(list)\n",
    "\n",
    "        count = [1]*n #统计子树节点数，每个子结点初始化为1\n",
    "        degree = [0]*n  #统计入度\n",
    "        for i in range(1,n):\n",
    "            edges[i].append(parents[i]) # i统计i的父节点\n",
    "            edges2[parents[i]].append(i) #统计parents[i]的子节点\n",
    "            degree[parents[i]] += 1 #计算parents[i]的入度\n",
    "        queue = collections.deque()\n",
    "        for i in range(n):\n",
    "            if degree[i] == 0:\n",
    "                queue.append(i)\n",
    "        ans = 0 #记录最大值\n",
    "        cnt = 0 #记录最大值的节点数\n",
    "        # print(degree)\n",
    "        while queue:\n",
    "            x = queue.popleft()\n",
    "            zishu = 0\n",
    "            tmp_ans = 1\n",
    "            for y in edges[x]:#先将父节点的入度-1\n",
    "                degree[y] -= 1\n",
    "                if degree[y] == 0:\n",
    "                    queue.append(y)\n",
    "            for y in edges2[x]: #依次乘子结点的个数，并统计子结点个数\n",
    "                zishu += count[y]\n",
    "                tmp_ans *= count[y]\n",
    "            count[x] += zishu\n",
    "            qita = n - 1 - zishu\n",
    "            if qita >0:\n",
    "                tmp_ans *= qita\n",
    "            # print(x,zishu,qita,tmp_ans,queue,degree)\n",
    "            if ans == tmp_ans:\n",
    "                cnt += 1\n",
    "            elif ans < tmp_ans:\n",
    "                ans = tmp_ans\n",
    "                cnt = 1\n",
    "        return cnt\n",
    "            \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        # 拓扑排序\n",
    "        # 记录当前节点的子树个数，从叶节点往上推\n",
    "        n = len(parents)\n",
    "        edges = defaultdict(list)\n",
    "        edges2 = defaultdict(list)\n",
    "\n",
    "        count = [1]*n #统计子树节点数\n",
    "        degree = [0]*n  #统计入度\n",
    "        for i in range(1,n):\n",
    "            edges[i].append(parents[i])\n",
    "            edges2[parents[i]].append(i)\n",
    "            degree[parents[i]] += 1\n",
    "        queue = collections.deque()\n",
    "        for i in range(n):\n",
    "            if degree[i] == 0:\n",
    "                queue.append(i)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        # print(degree)\n",
    "        while queue:\n",
    "            x = queue.popleft()\n",
    "            zishu = 0\n",
    "            tmp_ans = 1\n",
    "            for y in edges[x]:\n",
    "                degree[y] -= 1\n",
    "                if degree[y] == 0:\n",
    "                    queue.append(y)\n",
    "            for y in edges2[x]:\n",
    "                zishu += count[y]\n",
    "                tmp_ans *= count[y]\n",
    "            count[x] += zishu\n",
    "            qita = n - 1 - zishu\n",
    "            if qita >0:\n",
    "                tmp_ans *= qita\n",
    "            # print(x,zishu,qita,tmp_ans,queue,degree)\n",
    "            if ans == tmp_ans:\n",
    "                cnt += 1\n",
    "            elif ans < tmp_ans:\n",
    "                ans = tmp_ans\n",
    "                cnt = 1\n",
    "        return cnt\n",
    "            \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        num_ch_l, num_ch_r = [0] * n, [0] * n\n",
    "        ch_l, ch_r = [-1] * n, [-1] * n\n",
    "        for i in range(1, n):\n",
    "            pa = parents[i]\n",
    "            if ch_l[pa] == -1: ch_l[pa] = i\n",
    "            else: ch_r[pa] = i\n",
    "        \n",
    "        def dfs(root):\n",
    "            if root == -1: return 0\n",
    "            num_ch_l[root] = dfs(ch_l[root])\n",
    "            num_ch_r[root] = dfs(ch_r[root])\n",
    "            return num_ch_l[root] + num_ch_r[root] + 1\n",
    "        \n",
    "        dfs(0)\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for l, r in zip(num_ch_l, num_ch_r):\n",
    "            s = n - l - r - 1\n",
    "            res = max(1, s) * max(1, l) * max(1, r)\n",
    "            cnt[res] += 1\n",
    "            ans = max(ans, res)\n",
    "        return cnt[ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        ans = 0\n",
    "        max_score = -inf\n",
    "        tree = [[-1,-1] for _ in range(n)]\n",
    "        def build(tree):\n",
    "            for i in range(1, n):\n",
    "                parent_i = parents[i]\n",
    "                if tree[parent_i][0] == -1:\n",
    "                    tree[parent_i][0] = i \n",
    "                else:\n",
    "                    tree[parent_i][1] = i \n",
    "        \n",
    "        build(tree)\n",
    "        \n",
    "        def traverse(idx):\n",
    "            nonlocal ans, max_score, n, tree\n",
    "            if idx == -1:\n",
    "                return 0\n",
    "            left = traverse(tree[idx][0])\n",
    "            right = traverse(tree[idx][1])\n",
    "            score = max(left, 1) * max(right, 1) * max(n-left-right-1, 1)\n",
    "            if score > max_score:\n",
    "                ans = 1\n",
    "                max_score = score\n",
    "            elif score == max_score:\n",
    "                ans += 1\n",
    "            return left + right + 1\n",
    "        \n",
    "        traverse(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        self.buildTree(parents)\n",
    "        self.all_tree_nodes = len(parents)\n",
    "\n",
    "        self.counter = defaultdict(list)\n",
    "\n",
    "        self.countNode(0)\n",
    "\n",
    "        return len(self.counter[max(self.counter)])\n",
    "\n",
    "    def countNode(self, root):\n",
    "        if root == -1:\n",
    "            return 0 \n",
    "\n",
    "        left_nodes = self.countNode(self.tree[root][0])\n",
    "        right_nodes = self.countNode(self.tree[root][1])\n",
    "\n",
    "        other_nodes = self.all_tree_nodes - left_nodes - right_nodes - 1\n",
    "\n",
    "        score = max(1, left_nodes) * max(1, right_nodes) * max(1, other_nodes)\n",
    "\n",
    "        self.counter[score].append(root)\n",
    "\n",
    "        return left_nodes + right_nodes + 1\n",
    "\n",
    "    def buildTree(self, parents):\n",
    "        n = len(parents)\n",
    "\n",
    "        tree = [[-1, -1] for _ in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            pat = parents[i]\n",
    "\n",
    "            if tree[pat][0] == -1:\n",
    "                tree[pat][0] = i\n",
    "            else:\n",
    "                tree[pat][1] = i\n",
    "\n",
    "        self.tree = tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        if not parents:\n",
    "            return 0\n",
    "        n = len(parents)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for i in range(1, len(parents)):\n",
    "            graph[parents[i]].append(i)\n",
    "        \n",
    "        maxscore, ans = 0, 0\n",
    "        \n",
    "        def traverse(root):\n",
    "            nonlocal maxscore, ans\n",
    "            if graph[root]:\n",
    "                left = traverse(graph[root][0])\n",
    "            else:\n",
    "                left = 0\n",
    "            if len(graph[root]) == 2:\n",
    "                right = traverse(graph[root][1])\n",
    "            else:\n",
    "                right = 0\n",
    "            \n",
    "            score = max(1, (len(graph)-left-right-1)) * max(1, left) * max(1, right)\n",
    "            if score > maxscore:\n",
    "                maxscore, ans = score, 1\n",
    "            elif score == maxscore:\n",
    "                ans += 1\n",
    "            return left + right + 1\n",
    "        \n",
    "        traverse(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        ans = 0\n",
    "        max_score = -inf\n",
    "        tree = [[-1,-1] for _ in range(n)]\n",
    "        def build(tree):\n",
    "            for i in range(1, n):\n",
    "                parent_i = parents[i]\n",
    "                if tree[parent_i][0] == -1:\n",
    "                    tree[parent_i][0] = i \n",
    "                else:\n",
    "                    tree[parent_i][1] = i \n",
    "        \n",
    "        build(tree)\n",
    "        print(tree)\n",
    "        \n",
    "        def traverse(idx):\n",
    "            nonlocal ans, max_score, n, tree\n",
    "            if idx == -1:\n",
    "                return 0\n",
    "            left = traverse(tree[idx][0])\n",
    "            right = traverse(tree[idx][1])\n",
    "            score = max(left, 1) * max(right, 1) * max(n-left-right-1, 1)\n",
    "            if score > max_score:\n",
    "                ans = 1\n",
    "                max_score = score\n",
    "            elif score == max_score:\n",
    "                ans += 1\n",
    "            return left + right + 1\n",
    "        \n",
    "        traverse(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for node, p in enumerate(parents[1:], 1):\n",
    "            tree[p].append(node)\n",
    "        print(tree)\n",
    "\n",
    "        n = len(tree)\n",
    "        max_score = 0\n",
    "        res = 0\n",
    "        def dfs(root: int):\n",
    "            nonlocal max_score, res\n",
    "            left = dfs(tree[root][0]) if tree[root] else 0\n",
    "            right = dfs(tree[root][1]) if len(tree[root]) == 2 else 0\n",
    "            if (score := max(1, (n - left - right - 1)) * max(1, left) * max(1, right)) > max_score:\n",
    "                max_score, res = score, 1\n",
    "            elif score == max_score:\n",
    "                res += 1\n",
    "            return left+right+1\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        def dfs(cur):\n",
    "            cnt = 1\n",
    "            score = 1\n",
    "            for nxt in graph[cur]:\n",
    "                tmp = dfs(nxt)\n",
    "                cnt += tmp\n",
    "                score *= tmp\n",
    "            if n > cnt:\n",
    "                score *= n - cnt\n",
    "\n",
    "            nonlocal max_score, max_cnt\n",
    "            if score > max_score:\n",
    "                max_score, max_cnt = score, 1\n",
    "            elif score == max_score:\n",
    "                max_cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        n = len(parents)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for nxt, cur in enumerate(parents):\n",
    "            if cur > -1:\n",
    "                graph[cur].append(nxt)\n",
    "\n",
    "        max_score, max_cnt = -1, 0\n",
    "        dfs(0)\n",
    "        return max_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "       def dfs(x: int) -> int:\n",
    "          s = 0\n",
    "          cur = 1\n",
    "          for y in g[x]:\n",
    "             cnt = dfs(y)\n",
    "             cur *= cnt\n",
    "             s += cnt\n",
    "          if n - s - 1 != 0:\n",
    "             cur *= n - s - 1\n",
    "          nonlocal res, max_score\n",
    "          if cur > max_score:\n",
    "             max_score = cur\n",
    "             res = 1\n",
    "          elif cur == max_score:\n",
    "             res += 1\n",
    "          return s + 1\n",
    "       n = len(parents)\n",
    "       g = [[] for _ in range(n)]\n",
    "       for i in range(1, n):\n",
    "          g[parents[i]].append(i)\n",
    "       res = 0\n",
    "       max_score = 0\n",
    "       dfs(0)\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        childrens = [[]for _ in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                childrens[p].append(i)\n",
    "        \n",
    "        max_score, cnt = 0, 0\n",
    "\n",
    "        # 计算size的方法十分巧妙\n",
    "        def dfs(node):\n",
    "            score = 1\n",
    "            children_size = 0\n",
    "            for ch in childrens[node]:\n",
    "                sz = dfs(ch)\n",
    "                score *= sz\n",
    "                children_size += sz\n",
    "            if node != 0:\n",
    "                score *= (n - 1 - children_size)\n",
    "            nonlocal max_score, cnt\n",
    "            if score == max_score:\n",
    "                cnt += 1\n",
    "            elif score > max_score:\n",
    "                max_score, cnt = score, 1\n",
    "            return children_size + 1\n",
    "        \n",
    "        dfs(0)\n",
    "        return cnt\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            g[parents[i]].append(i)\n",
    "        res = 0\n",
    "        maxScore = 0\n",
    "        def dfs(x):\n",
    "            nonlocal res, maxScore\n",
    "            size, score = 1, 1\n",
    "\n",
    "            for ch in g[x]:\n",
    "                ch_size = dfs(ch)\n",
    "                score *= ch_size\n",
    "                size += ch_size\n",
    "\n",
    "            # x不是根节点\n",
    "            if x > 0:\n",
    "                score *= n - size\n",
    "\n",
    "            if score > maxScore:\n",
    "                maxScore, res = score, 1\n",
    "            elif score == maxScore:\n",
    "                res += 1\n",
    "\n",
    "            return size\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parents[i]].append(i)\n",
    "        ret = 0\n",
    "        retcnt = 0\n",
    "        \n",
    "        def dfs(node):\n",
    "            nonlocal ret, retcnt\n",
    "            m = 1\n",
    "            cnt = 1\n",
    "            for son in g[node]:\n",
    "                c = dfs(son)\n",
    "                m *= c\n",
    "                cnt += c\n",
    "            if n - cnt > 0:\n",
    "                m *= (n - cnt)\n",
    "            if ret < m:\n",
    "                ret, retcnt = m, 1\n",
    "            elif ret == m:\n",
    "                retcnt += 1\n",
    "            return cnt\n",
    "        dfs(0)\n",
    "        return retcnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "       def dfs(x: int) -> int:\n",
    "          s = 0\n",
    "          cur = 1\n",
    "          for y in g[x]:\n",
    "             cnt = dfs(y)\n",
    "             cur *= cnt\n",
    "             s += cnt\n",
    "          # 考虑根节点的情况\n",
    "          if n - s - 1 != 0:\n",
    "             cur *= n - s - 1\n",
    "          nonlocal res, max_score\n",
    "          if cur > max_score:\n",
    "             max_score = cur\n",
    "             res = 1\n",
    "          elif cur == max_score:\n",
    "             res += 1\n",
    "          return s + 1\n",
    "       n = len(parents)\n",
    "       g = [[] for _ in range(n)]\n",
    "       for i, v in enumerate(parents):\n",
    "           if i:\n",
    "             g[v].append(i)\n",
    "       res = 0\n",
    "       max_score = 0\n",
    "       dfs(0)\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        children = [[] for _ in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            children[p].append(i)\n",
    "\n",
    "        sizes = [1] * n\n",
    "\n",
    "        def dfs(node=0):\n",
    "            if len(children[node]) == 0:\n",
    "                sizes[node] = 1\n",
    "            for c in children[node]:\n",
    "                dfs(c)\n",
    "                sizes[node] += sizes[c]\n",
    "\n",
    "        dfs(0)\n",
    "        scores = []\n",
    "        for i in range(n):\n",
    "            cur = 1\n",
    "            for c in children[i]:\n",
    "                cur *= sizes[c]\n",
    "            if parents[i] != -1:\n",
    "                cur *= sizes[0] - sizes[i]\n",
    "            scores.append(cur)\n",
    "        max_score = max(scores)\n",
    "        res = 0\n",
    "        for s in scores:\n",
    "            res += 1 if s == max_score else 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        # 稍微记录一下左右子树就行了\n",
    "        n = len(parents)\n",
    "        m = defaultdict(int)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in enumerate(parents):\n",
    "            if v != -1:\n",
    "                g[v].append(u)\n",
    "        \n",
    "        def dfs(root):\n",
    "            if not g[root]:\n",
    "                left, right = 0, 0\n",
    "            elif len(g[root]) == 1:\n",
    "                l, r = dfs(g[root][0])\n",
    "                left, right = 1 + l+r, 0\n",
    "            else:\n",
    "                l1, r1 = dfs(g[root][0])\n",
    "                l2, r2 = dfs(g[root][1])\n",
    "                left, right = 1+l1+r1, 1+l2+r2\n",
    "            v = max(left, 1) * max(right, 1) * max(n-left-right-1, 1)\n",
    "            m[v] += 1\n",
    "            return left, right\n",
    "        \n",
    "        dfs(0)\n",
    "        return m[max(m.keys())]\n",
    "        \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "\n",
    "        def DFS(root):\n",
    "            if root not in child_map: # 节点是叶子节点\n",
    "                num_upper = n - 1\n",
    "                ans_map[num_upper] += 1\n",
    "                return 1\n",
    "            elif len(child_map[root]) == 1: # 节点只有一个child\n",
    "                num_left = DFS(child_map[root][0])\n",
    "                num_upper = n - num_left - 1 if root != 0 else 1\n",
    "                ans_map[num_left * num_upper] += 1\n",
    "                return num_left + 1\n",
    "            else: # 节点有两个child\n",
    "                num_left = DFS(child_map[root][0])\n",
    "                num_right = DFS(child_map[root][1])\n",
    "                num_upper = n - num_left - num_right- 1 if root != 0 else 1\n",
    "                ans_map[num_left * num_right * num_upper] += 1\n",
    "                return num_left + num_right + 1\n",
    "\n",
    "        n, child_map, ans_map = len(parents), defaultdict(list), defaultdict(int)\n",
    "        for child, parent in enumerate(parents): # 建图\n",
    "            child_map[parent].append(child)\n",
    "        \n",
    "        DFS(0)\n",
    "        ans = list(ans_map.items())\n",
    "        ans.sort(reverse = True)\n",
    "        return ans[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        N = len(parents)\n",
    "        self.subtrees = [1] * N\n",
    "        self.tree = [[] for _ in range(N)]\n",
    "\n",
    "        for p in range(N):\n",
    "            if parents[p] != -1:\n",
    "                self.tree[parents[p]].append(p)\n",
    "\n",
    "        self.traverse(self.tree, 0)\n",
    "        max_score = 0\n",
    "        scores = []\n",
    "        for i in range(N):\n",
    "            score = max(self.subtrees[0] - self.subtrees[i], 1)\n",
    "            for child in self.tree[i]:\n",
    "                score = score * self.subtrees[child]\n",
    "            scores.append(score)\n",
    "            max_score = max(max_score, score)\n",
    "        return scores.count(max_score)\n",
    "        \n",
    "\n",
    "    def traverse(self, root, r):\n",
    "        if not root[r]:\n",
    "            return 1\n",
    "        subs = 1\n",
    "        for child in root[r]:\n",
    "            subs += self.traverse(root, child)\n",
    "        self.subtrees[r] = subs\n",
    "        return subs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.aux = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        nodes = [Node(i) for i in range(len(parents))]\n",
    "        \n",
    "        for i in range(len(parents)):\n",
    "            if parents[i] == -1:\n",
    "                head = nodes[i]\n",
    "            elif nodes[parents[i]].left:\n",
    "                nodes[parents[i]].right = nodes[i]\n",
    "            else:\n",
    "                nodes[parents[i]].left = nodes[i]\n",
    "        \n",
    "        max_val = -1\n",
    "        count = 0\n",
    "        \n",
    "        def dfs(node):\n",
    "            nonlocal max_val\n",
    "            nonlocal count\n",
    "            if node is None:\n",
    "                return 0\n",
    "            nl = dfs(node.left)\n",
    "            nr = dfs(node.right)\n",
    "            nv = max(nl, 1) * max(nr, 1) * max(len(parents) - nl - nr - 1, 1)\n",
    "            print(node.val, nv)\n",
    "            if nv > max_val:\n",
    "                count = 1\n",
    "                max_val = nv\n",
    "            elif nv == max_val:\n",
    "                count += 1\n",
    "            return nl + nr + 1\n",
    "        \n",
    "        dfs(head)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\r\n",
    "        n = len(parents)\r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        for i, x in enumerate(parents[1:], 1):\r\n",
    "            g[x].append(i)\r\n",
    "        score = [0] * (n)\r\n",
    "        # print(g)\r\n",
    "\r\n",
    "        def dfs(x: int):\r\n",
    "            if len(g[x]) == 0:\r\n",
    "                score[x] = n - 1\r\n",
    "                return 1 \r\n",
    "            res = 0 \r\n",
    "            s = 1\r\n",
    "            for y in g[x]:\r\n",
    "                dy = dfs(y)\r\n",
    "                res += dy\r\n",
    "                s *= dy\r\n",
    "            if parents[x] == -1:\r\n",
    "                score[x] = s \r\n",
    "            else :\r\n",
    "                score[x] = (n - res - 1) * s \r\n",
    "            return res + 1\r\n",
    "        dfs(0)\r\n",
    "        mx = max(score)\r\n",
    "        return sum(x == mx for x in score) \r\n",
    "    \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n=len(parents)\n",
    "        nums=[0]*n #以自己为子树的根的节点数\n",
    "        children=[[]for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            children[parents[i]].append(i)\n",
    "        def dfs(index):\n",
    "            if nums[index]!=0:\n",
    "                return nums[index]\n",
    "            res=1\n",
    "            for child in children[index]:\n",
    "                res+=dfs(child)\n",
    "            nums[index]=res\n",
    "            return res\n",
    "        nowMax=0\n",
    "        nowCount=0\n",
    "        for i in range(n):\n",
    "            tmp=1\n",
    "            for child in children[i]:\n",
    "                tmp*=dfs(child)\n",
    "            if parents[i]!=-1:\n",
    "                tmp*=(n-dfs(i))\n",
    "            if tmp>nowMax:\n",
    "                nowMax=tmp\n",
    "                nowCount=1\n",
    "            elif tmp==nowMax:\n",
    "                nowCount+=1\n",
    "        return nowCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n=len(parents)\n",
    "        nums=[0]*n #以自己为子树的根的节点数\n",
    "        children=[[]for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            children[parents[i]].append(i)\n",
    "        def dfs(index):\n",
    "            if nums[index]!=0:\n",
    "                return nums[index]\n",
    "            res=1\n",
    "            for child in children[index]:\n",
    "                res+=dfs(child)\n",
    "            nums[index]=res\n",
    "            return res\n",
    "        nowMax=0\n",
    "        nowCount=0\n",
    "        for i in range(n):\n",
    "            tmp=1\n",
    "            for child in children[i]:\n",
    "                tmp*=dfs(child)\n",
    "            if parents[i]!=-1:\n",
    "                tmp*=(n-dfs(i))\n",
    "            print(i,tmp)\n",
    "            if tmp>nowMax:\n",
    "                nowMax=tmp\n",
    "                nowCount=1\n",
    "            elif tmp==nowMax:\n",
    "                nowCount+=1\n",
    "        return nowCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        def DFS(i):\n",
    "            remain_nodes = n - 1\n",
    "            score = 1\n",
    "            for c in childs[i]:\n",
    "                subtree_nodes = DFS(c)\n",
    "                score *= subtree_nodes\n",
    "                remain_nodes -= subtree_nodes\n",
    "            if i != 0:\n",
    "                score *= remain_nodes\n",
    "            nonlocal score_max\n",
    "            nonlocal max_count\n",
    "            if score > score_max:\n",
    "                score_max = score\n",
    "                max_count = 1\n",
    "            elif score == score_max:\n",
    "                max_count += 1\n",
    "            return n - remain_nodes\n",
    "\n",
    "        n = len(parents)\n",
    "        childs = [[] for _ in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                childs[p].append(i)\n",
    "\n",
    "        score_max = 0\n",
    "        max_count = 0\n",
    "        DFS(0)\n",
    "        return max_count\n",
    "\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in enumerate(parents):\n",
    "            if y != -1:\n",
    "                g[y].append(x)\n",
    "        \n",
    "        ans = mx = 0\n",
    "        \n",
    "        def dfs(x: int, p: int) -> int:\n",
    "            nonlocal ans, mx\n",
    "            s = 1\n",
    "            sz = 1\n",
    "            for y in g[x]:\n",
    "                t = dfs(y, x)\n",
    "                sz += t\n",
    "                s *= t\n",
    "            if p != -1:\n",
    "                s *= n - sz\n",
    "            if s > mx:\n",
    "                mx = s\n",
    "                ans = 1\n",
    "            elif s == mx:\n",
    "                ans += 1\n",
    "            return sz\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        children = [[] for _ in range(n)]\n",
    "        for node, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                children[p].append(node)\n",
    "\n",
    "        maxScore, cnt = 0, 0\n",
    "        def dfs(node: int) -> int:\n",
    "            score = 1\n",
    "            size = n - 1\n",
    "            for ch in children[node]:\n",
    "                sz = dfs(ch)\n",
    "                score *= sz\n",
    "                size -= sz\n",
    "            if node != 0:\n",
    "                score *= size\n",
    "            nonlocal maxScore, cnt\n",
    "            if score == maxScore:\n",
    "                cnt += 1\n",
    "            elif score > maxScore:\n",
    "                maxScore, cnt = score, 1\n",
    "            return n - size\n",
    "        dfs(0)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        child = [[] for _ in range(n)]\n",
    "\n",
    "        for i, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                child[p].append(i)\n",
    "        \n",
    "        ans, cnt = 0, 0\n",
    "\n",
    "        # 返回以x为根节点的树的节点数\n",
    "        def dfs(x):\n",
    "            nonlocal ans, cnt\n",
    "            # 除自己外的节点个数\n",
    "            cur = 1\n",
    "            size = n - 1\n",
    "            # 逐个计算子树的size，并且累加结果\n",
    "            for y in child[x]:\n",
    "                sz = dfs(y)\n",
    "                size -= sz\n",
    "                cur *= sz\n",
    "            # 如果是不是根节点，还需要*size\n",
    "            if x != 0:\n",
    "                cur *= size\n",
    "            # 看cur和ans的大小维护结果\n",
    "            if cur == ans:\n",
    "                cnt += 1\n",
    "            if cur > ans:\n",
    "                ans, cnt = cur, 1\n",
    "            \n",
    "            # 返回以x为根的子树的大小,父节点分支的大小是size,那么x为根的子树是n-size\n",
    "            return n - size\n",
    "        \n",
    "        dfs(0)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        children = [[] for _ in range(n)]\n",
    "        for node, parent in enumerate(parents):\n",
    "            if parent != -1:\n",
    "                children[parent].append(node)\n",
    "\n",
    "        self.max_score = 0\n",
    "        self.cnt = 0\n",
    "        def dfs(node):\n",
    "            score = 1\n",
    "            size = n - 1\n",
    "            for child in children[node]:\n",
    "                sz = dfs(child)\n",
    "                score *= sz\n",
    "                size -= sz\n",
    "            if node != 0:\n",
    "                score *= size\n",
    "            if score == self.max_score:\n",
    "                self.cnt += 1\n",
    "            elif score > self.max_score:\n",
    "                self.max_score = score\n",
    "                self.cnt = 1\n",
    "            return n - size\n",
    "\n",
    "        dfs(0)\n",
    "        return self.cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        children = [[] for _ in range(n)]\n",
    "        for node, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                children[p].append(node)\n",
    "\n",
    "        maxScore, cnt = 0, 0\n",
    "        def dfs(node: int) -> int:\n",
    "            score = 1\n",
    "            size = n - 1\n",
    "            for ch in children[node]:\n",
    "                sz = dfs(ch)\n",
    "                score *= sz\n",
    "                size -= sz\n",
    "            if node != 0:\n",
    "                score *= size\n",
    "            nonlocal maxScore, cnt\n",
    "            if score == maxScore:\n",
    "                cnt += 1\n",
    "            elif score > maxScore:\n",
    "                maxScore, cnt = score, 1\n",
    "            return n - size\n",
    "        dfs(0)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "       \n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for w in range(1, n):\n",
    "            v = parents[w]\n",
    "            g[v].append(w)\n",
    "\n",
    "        maxScore = [0]\n",
    "\n",
    "        def dfs(v):\n",
    "            size, score = 1, 1\n",
    "            for w in g[v]:\n",
    "                sz = dfs(w)\n",
    "                size += sz\n",
    "                score *= sz\n",
    "\n",
    "            if v > 0:\n",
    "                score *= n - size\n",
    "\n",
    "            if score > maxScore[0]:\n",
    "                maxScore[0], ans[0] = score, 1\n",
    "            elif score == maxScore[0]:\n",
    "                ans[0] += 1\n",
    "\n",
    "            return size\n",
    "\n",
    "        ans = [0]\n",
    "        dfs(0)\n",
    "        return ans[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        childrens = [[]for _ in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                childrens[p].append(i)\n",
    "        \n",
    "        max_score, cnt = 0, 0\n",
    "\n",
    "        # 计算size的方法十分巧妙\n",
    "        def dfs(node):\n",
    "            score = 1\n",
    "            size = n - 1 # 减去自己\n",
    "            for ch in childrens[node]:\n",
    "                sz = dfs(ch)\n",
    "                score *= sz\n",
    "                size -= sz\n",
    "            if node != 0:\n",
    "                score *= size # 现在的size减去了子树的size\n",
    "            nonlocal max_score, cnt\n",
    "            if score == max_score:\n",
    "                cnt += 1\n",
    "            elif score > max_score:\n",
    "                max_score, cnt = score, 1\n",
    "            return n - size\n",
    "        \n",
    "        dfs(0)\n",
    "        return cnt\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for node, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                g[p].append(node)\n",
    "\n",
    "        maxScore, cnt = 0, 0\n",
    "        def dfs(node: int) -> int:\n",
    "            score = 1\n",
    "            size = n - 1\n",
    "            for ch in g[node]:\n",
    "                sz = dfs(ch)\n",
    "                score *= sz\n",
    "                size -= sz\n",
    "            if node != 0:\n",
    "                score *= size\n",
    "            nonlocal maxScore, cnt\n",
    "            if score == maxScore:\n",
    "                cnt += 1\n",
    "            elif score > maxScore:\n",
    "                maxScore, cnt = score, 1\n",
    "            return n - size\n",
    "        dfs(0)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n, max_value, ans = len(parents), 0, 0\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if i == 0: continue\n",
    "            g[p].append(i)\n",
    "\n",
    "        def dfs(node: int) -> int:\n",
    "            nonlocal ans, max_value\n",
    "            child_size = 0\n",
    "            value = 1\n",
    "            for nxt in g[node]:\n",
    "                size = dfs(nxt)\n",
    "                child_size += size\n",
    "                value *= size\n",
    "            value *= max(n - child_size - 1, 1)\n",
    "            if value > max_value:\n",
    "                ans = 1\n",
    "                max_value = value\n",
    "            elif value == max_value:\n",
    "                ans += 1\n",
    "\n",
    "            return child_size + 1\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i,p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                g[p].append(i)\n",
    "        cnt = [1]*n\n",
    "        def dfs(cur:int)->int:\n",
    "            nonlocal g\n",
    "            nonlocal cnt\n",
    "            if not g[cur]:\n",
    "                return cnt[cur]\n",
    "\n",
    "            for x in g[cur]:\n",
    "                cnt[cur] += dfs(x)\n",
    "\n",
    "            return cnt[cur]\n",
    "\n",
    "        dfs(0)\n",
    "        freq = Counter()\n",
    "        for i in range(n):\n",
    "            ans = 1\n",
    "            if parents[i] != -1:\n",
    "                ans *= n - cnt[i]\n",
    "\n",
    "            for x in g[i]:\n",
    "                ans *= cnt[x]\n",
    "\n",
    "            freq[ans] += 1\n",
    "\n",
    "        return freq[max(freq.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n=len(parents)\n",
    "        scores=[1]*n\n",
    "        children=[[] for _ in range(n)]\n",
    "        root=-1\n",
    "        for i,p in enumerate(parents):\n",
    "            if p!=-1:\n",
    "                children[p].append(i)\n",
    "            else:\n",
    "                root=i\n",
    "        # print(children)\n",
    "        def dfs(node):\n",
    "            ret=1\n",
    "            for c in children[node]:\n",
    "                t=dfs(c)\n",
    "                scores[node] *=t\n",
    "                ret+=t\n",
    "            if n-ret>0:\n",
    "                scores[node]*=n-ret\n",
    "            return ret\n",
    "        dfs(root)\n",
    "        # print(scores)\n",
    "        cnt=Counter(scores)\n",
    "        # print(cnt)\n",
    "        return cnt[max(cnt.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n=len(parents)\n",
    "        scores=[1]*n\n",
    "        children=[[] for _ in range(n)]\n",
    "        root=0\n",
    "        max_score=-inf\n",
    "        for i in range(1,n):\n",
    "            children[parents[i]].append(i)\n",
    "        # print(children)\n",
    "        def dfs(node):\n",
    "            nonlocal max_score\n",
    "            ret=1\n",
    "            for c in children[node]:\n",
    "                t=dfs(c)\n",
    "                scores[node] *=t\n",
    "                ret+=t\n",
    "            if n-ret>0:\n",
    "                scores[node]*=n-ret\n",
    "            max_score=max(max_score,scores[node])\n",
    "            return ret\n",
    "        dfs(root)\n",
    "\n",
    "        return sum(s==max_score for s in scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        tree = [[] for _ in range(len(parents))]\n",
    "        count = [[] for _ in range(len(parents))]\n",
    "        for i in range(1, len(parents)):\n",
    "            tree[parents[i]].append(i)\n",
    "\n",
    "        def travel(index):\n",
    "            nonlocal count, tree\n",
    "            if len(tree[index]) == 0:\n",
    "                count[index] = 1\n",
    "                return 1\n",
    "            c = 1\n",
    "            for i in tree[index]:\n",
    "                c += travel(i)\n",
    "            count[index] = c\n",
    "            return c\n",
    "\n",
    "        travel(0)\n",
    "\n",
    "        maxcount = count[0]\n",
    "        maxscore = 0\n",
    "        results = []\n",
    "        for i in range(len(parents)):\n",
    "            score = maxcount - count[i]\n",
    "            if score == 0:\n",
    "                score = 1\n",
    "            for j in tree[i]:\n",
    "                score *= count[j]\n",
    "\n",
    "            if score==maxscore:\n",
    "                results.append(i)\n",
    "            if score>maxscore:\n",
    "                maxscore=score\n",
    "                results = []\n",
    "                results.append(i)\n",
    "        return len(results)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: [int]) -> int:\n",
    "        nn=len(parents)\n",
    "        road = [[] for i in range(nn)]\n",
    "        for i in range(1,nn):\n",
    "            road[parents[i]].append(i)\n",
    "            road[i].append(parents[i])\n",
    "\n",
    "        maxscore=-1\n",
    "        maxscorenumber=0\n",
    "        dp=[ 0 for i in range(nn)]\n",
    "        def dfs(x: int, fa: int) -> int:\n",
    "            nonlocal road,maxscore,maxscorenumber\n",
    "            sonXs = 1\n",
    "            sonnumber = 0\n",
    "            for y in road[x]:\n",
    "                if y != fa:\n",
    "                    cursons=dfs(y, x)       #计算以y为根的子树的节点数目\n",
    "                    sonnumber+=cursons\n",
    "                    if cursons>1: sonXs*=cursons\n",
    "\n",
    "            patree=nn-1-sonnumber\n",
    "            if patree>1: sonXs*=patree\n",
    "\n",
    "            if sonXs>maxscore:\n",
    "                maxscore=sonXs\n",
    "                maxscorenumber=1\n",
    "            elif sonXs==maxscore:\n",
    "                maxscorenumber+=1\n",
    "\n",
    "            dp[x]=sonnumber+1\n",
    "            return sonnumber+1\n",
    "\n",
    "        dfs(0, -1)\n",
    "#        print(dp)\n",
    "#        print(maxscore)\n",
    "        return maxscorenumber\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n=len(parents)\n",
    "        scores=[1]*n\n",
    "        children=[[] for _ in range(n)]\n",
    "        root=-1\n",
    "        max_score=-inf\n",
    "        for i,p in enumerate(parents):\n",
    "            if p!=-1:\n",
    "                children[p].append(i)\n",
    "            else:\n",
    "                root=i\n",
    "        # print(children)\n",
    "        def dfs(node):\n",
    "            nonlocal max_score\n",
    "            ret=1\n",
    "            for c in children[node]:\n",
    "                t=dfs(c)\n",
    "                scores[node] *=t\n",
    "                ret+=t\n",
    "            if n-ret>0:\n",
    "                scores[node]*=n-ret\n",
    "            max_score=max(max_score,scores[node])\n",
    "            return ret\n",
    "        dfs(root)\n",
    "\n",
    "        return sum(s==max_score for s in scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        n = len(parents)\n",
    "        for i in range(n):\n",
    "            if parents[i] >= 0:\n",
    "                g[parents[i]].append(i)\n",
    "        #print(g)\n",
    "        ans = []\n",
    "\n",
    "        def dfs(idx):\n",
    "            if idx not in g:\n",
    "                ans.append(n-1)\n",
    "                return 1\n",
    "            left = dfs(g[idx][0])\n",
    "            if len(g[idx]) == 2:\n",
    "                right = dfs(g[idx][1])\n",
    "            else:\n",
    "                right = 0\n",
    "            x = left\n",
    "            if n-left-right-1> 0:\n",
    "                z = n-left-right-1\n",
    "            else:\n",
    "                z = 1\n",
    "            if right>0:\n",
    "                y = right\n",
    "            else:\n",
    "                y = 1\n",
    "            ans.append(x*y*z)\n",
    "            \n",
    "            return left+right+1\n",
    "        \n",
    "        dfs(0)\n",
    "        #print(ans)\n",
    "        ma = 0\n",
    "        cnt = 0\n",
    "        for i in ans:\n",
    "            if i==ma:\n",
    "                cnt += 1\n",
    "            elif i>ma:\n",
    "                ma = i\n",
    "                cnt = 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n=len(parents)\n",
    "        dct=[[]for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            dct[parents[i]].append(i)\n",
    "        cnt=Counter()\n",
    "        def dfs(r):\n",
    "            res=1\n",
    "            c=1\n",
    "            for x in dct[r]:\n",
    "                y=dfs(x)\n",
    "                res*=y\n",
    "                c+=y\n",
    "            cnt[res*(max(1,n-c))]+=1\n",
    "            print(r,res*(max(1,n-c)))\n",
    "            return c\n",
    "        dfs(0)\n",
    "        ans=0\n",
    "\n",
    "        ma=0\n",
    "        for x in cnt:\n",
    "            ma=max(ma,x)\n",
    "\n",
    "        return cnt[ma]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        def traverse(tree, cur):\n",
    "            count = 1\n",
    "            for i in tree[cur]:\n",
    "                # if i == pre:\n",
    "                #     continue\n",
    "                count += traverse(tree, i)\n",
    "            tree_node[cur] = count\n",
    "            return count \n",
    "\n",
    "        tree = defaultdict(list)\n",
    "        for i, x in enumerate(parents):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            # tree[i].append(x)\n",
    "            tree[x].append(i)\n",
    "        # print(tree)\n",
    "        tree_node = {}\n",
    "        traverse(tree, 0)\n",
    "        # print(tree_node)\n",
    "        max_val = count = 0\n",
    "        n = len(parents)\n",
    "        for i in range(n):\n",
    "            mul = cnt = 1\n",
    "            for j in tree[i]:\n",
    "                # if j == i:\n",
    "                #     continue\n",
    "                mul *= tree_node[j]\n",
    "                cnt += tree_node[j]\n",
    "            if cnt < n:\n",
    "                mul *= (n-cnt)\n",
    "            # print(cnt)\n",
    "            if mul > max_val:\n",
    "                max_val = mul\n",
    "                count = 1\n",
    "            elif mul == max_val:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in enumerate(parents):\n",
    "            if y != -1:\n",
    "                g[y].append(x)\n",
    "        \n",
    "        sz = [0] * n\n",
    "\n",
    "        def get_sz(x: int) -> int:\n",
    "            cnt = 1\n",
    "            for y in g[x]:\n",
    "                cnt += get_sz(y)\n",
    "            sz[x] = cnt\n",
    "            return cnt\n",
    "        \n",
    "        ans = mx = 0\n",
    "        def dfs(x: int, p: int) -> None:\n",
    "            nonlocal ans, mx\n",
    "            s = 1\n",
    "            if p != -1:\n",
    "                s *= sz[0] - sz[x]\n",
    "            for y in g[x]:\n",
    "                s *= sz[y]\n",
    "                dfs(y, x)\n",
    "            if s > mx:\n",
    "                mx = s\n",
    "                ans = 1\n",
    "            elif s == mx:\n",
    "                ans += 1\n",
    "        \n",
    "        get_sz(0)\n",
    "        dfs(0, -1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        children = [[] for _ in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                children[p].append(i)\n",
    "        \n",
    "        nums = [{} for i in range(n)]\n",
    "        \n",
    "\n",
    "        def dfs(x):\n",
    "            kids = children[x]\n",
    "            ans = 0\n",
    "\n",
    "            for k in kids:\n",
    "                d = dfs(k)\n",
    "                nums[x][k] = d\n",
    "                ans += d\n",
    "            \n",
    "            return ans + 1\n",
    "            \n",
    "\n",
    "        dfs(0)\n",
    "        ans = defaultdict(int)\n",
    "\n",
    "        for x, p in enumerate(parents):\n",
    "            res = 1\n",
    "            s = 0\n",
    "            for k in nums[x].values():\n",
    "                res *= k\n",
    "                s += k\n",
    "            if p != -1:\n",
    "                res *= n-s-1\n",
    "            \n",
    "            ans[res] += 1\n",
    "        \n",
    "        return ans[max(ans.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        nums = [0] * n \n",
    "        for i in range(1, n):\n",
    "            x, y = i, parents[i]\n",
    "            graph[y].append(x)\n",
    "        def dfs(x: int) -> int:\n",
    "            res = 1\n",
    "            for y in graph[x]:\n",
    "                res += dfs(y)\n",
    "            nums[x] = res\n",
    "            return res\n",
    "        dfs(0)\n",
    "        max_val = 0\n",
    "        cnt = 0\n",
    "        def reroot(x: int, fa: int) -> None:\n",
    "            res = 1\n",
    "            for y in graph[x]:\n",
    "                res *= nums[y]\n",
    "                reroot(y, x)\n",
    "            if fa != -1:\n",
    "                res *= (n - nums[x])\n",
    "            nonlocal max_val, cnt\n",
    "            if res > max_val:\n",
    "                max_val = res\n",
    "                cnt = 1\n",
    "            elif res == max_val:\n",
    "                cnt += 1\n",
    "        reroot(0, -1)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n=len(parents)\n",
    "        g=[[] for _ in parents]\n",
    "        for i,k in enumerate(parents):\n",
    "            if k!=-1:\n",
    "                g[k].append(i)\n",
    "        d=defaultdict(int)\n",
    "        res=[0]*n\n",
    "        def dfs(x):\n",
    "            arr=1\n",
    "            for i in g[x]:\n",
    "                arr+=dfs(i)\n",
    "            res[x]=arr\n",
    "            return arr\n",
    "        dfs(0)\n",
    "        def reroot(x,fa):\n",
    "            size=len(g[x])\n",
    "            arr=max(fa,1)\n",
    "            if size==0:\n",
    "                d[fa]+=1\n",
    "            elif size==1:\n",
    "                temp=res[g[x][0]]\n",
    "                d[arr*temp]+=1\n",
    "                reroot(g[x][0],fa+1)\n",
    "            else:\n",
    "                temp0,temp1=res[g[x][0]],res[g[x][1]]\n",
    "                d[arr*temp0*temp1]+=1\n",
    "                reroot(g[x][0],fa+1+temp1)\n",
    "                reroot(g[x][1],fa+1+temp0)\n",
    "        reroot(0,0)\n",
    "        return d[max(d.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        parent_to_son = defaultdict(list)\n",
    "        for i, j in enumerate(parents):\n",
    "            if j != -1:\n",
    "                parent_to_son[j].append(i)\n",
    "        nodes = [0]*n\n",
    "        nodes[0] = n\n",
    "        def dfs(node):\n",
    "            if len(parent_to_son[node]) == 0:\n",
    "                nodes[node] = 1\n",
    "                return nodes[node]\n",
    "            left = dfs(parent_to_son[node][0]) if len(parent_to_son[node]) > 0 else 0\n",
    "            right = dfs(parent_to_son[node][1]) if len(parent_to_son[node]) > 1 else 0\n",
    "            nodes[node] = left + right + 1\n",
    "            return nodes[node]\n",
    "        dfs(0)\n",
    "        res = list()\n",
    "        for i in range(n):\n",
    "            left = nodes[parent_to_son[i][0]] if len(parent_to_son[i]) > 0 else -1\n",
    "            right = nodes[parent_to_son[i][1]] if len(parent_to_son[i]) > 1 else -1\n",
    "            item = n\n",
    "            if left != -1:\n",
    "                item -= left\n",
    "            else:\n",
    "                left = 1\n",
    "            if right != -1:\n",
    "                item -= right\n",
    "            else:\n",
    "                right = 1\n",
    "            res.append((max(item - 1, 1)) * left * right)\n",
    "        \n",
    "        return Counter(res)[max(res)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        graph = defaultdict(list)\n",
    "        for i, p in enumerate(parents[1:], 1):\n",
    "            graph[p].append(i)\n",
    "        max_score, ans = 0, 0\n",
    "\n",
    "        def dfs(node):\n",
    "            left = dfs(graph[node][0]) if graph[node] else 0\n",
    "            right = dfs(graph[node][1]) if len(graph[node]) == 2 else 0\n",
    "            nonlocal max_score, ans\n",
    "            if (score := max(1, (n - left - right - 1)) * max(1, left) * max(1, right)) > max_score:\n",
    "                max_score, ans = score, 1\n",
    "            elif score == max_score:\n",
    "                ans += 1\n",
    "            return left + right + 1\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        # 其实就是写个递归统计一下左右一个结点左子树和右子树的结点个数\n",
    "        n = len(parents)\n",
    "        s = defaultdict(int)\n",
    "        t = [[-1, -1] for _ in range(n)]\n",
    "        for node, pa in enumerate(parents):\n",
    "            if pa != -1:\n",
    "                if t[pa][0] == -1:\n",
    "                    t[pa][0] = node\n",
    "                else:\n",
    "                    t[pa][1] = node\n",
    "        \n",
    "        def dfs(root):\n",
    "            if root == -1:\n",
    "                return -0.5, -0.5\n",
    "            ll, lr = dfs(t[root][0])\n",
    "            rl, rr = dfs(t[root][1])\n",
    "            l, r = ll + lr + 1, rl + rr + 1\n",
    "            s[root] = int(max(n-1-l-r, 1) * max(1, l) * max(1, r))\n",
    "            return l, r\n",
    "\n",
    "        dfs(root=0)\n",
    "        mx = max(s.values())\n",
    "        return sum(1 for k in s if s[k] == mx)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        graph = defaultdict(list)\n",
    "        for i, p in enumerate(parents[1:], 1):\n",
    "            graph[p].append(i)\n",
    "        max_score, ans = 0, 0\n",
    "\n",
    "        def dfs(node):\n",
    "            left = dfs(graph[node][0]) if graph[node] else 0\n",
    "            right = dfs(graph[node][1]) if len(graph[node]) == 2 else 0\n",
    "            nonlocal max_score, ans\n",
    "            if (score := max(1, (n - left - right - 1)) * max(1, left) * max(1, right)) > max_score:\n",
    "                max_score, ans = score, 1\n",
    "            elif score == max_score:\n",
    "                ans += 1\n",
    "            return left + right + 1\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        graph = defaultdict(list)\n",
    "        for i, p in enumerate(parents[1:], 1):\n",
    "            graph[p].append(i)\n",
    "        max_score, ans = 0, 0\n",
    "\n",
    "        def f(x):\n",
    "            nonlocal max_score, ans\n",
    "            left = f(graph[x][0]) if graph[x] else 0\n",
    "            right = f(graph[x][1]) if len(graph[x]) > 1 else 0\n",
    "            score = max(left, 1) * max(right, 1) * max(n - left - right - 1, 1)\n",
    "            if score > max_score:\n",
    "                max_score = score\n",
    "                ans = 1\n",
    "            elif score == max_score:\n",
    "                ans += 1\n",
    "            return left + right + 1\n",
    "        \n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "\n",
    "\n",
    "        n = len(parents)\n",
    "\n",
    "        total = 0 \n",
    "\n",
    "        trees = collections.defaultdict(list)\n",
    "        for i, x in enumerate(parents):\n",
    "            trees[x].append(i)\n",
    "        \n",
    "        cnt = 0 \n",
    "        max_score = 0 \n",
    "\n",
    "        def DFS(root):\n",
    "            nonlocal cnt \n",
    "            nonlocal max_score\n",
    "\n",
    "            below_cnt = 0\n",
    "            if len(trees[root])==0:\n",
    "                below_cnt  = 0\n",
    "                score = n-1 \n",
    "            \n",
    "            elif len(trees[root])==1:\n",
    "                below_cnt = DFS(trees[root][0])\n",
    "                score = (n-below_cnt-1)*below_cnt if n-below_cnt-1>0 else below_cnt\n",
    "            \n",
    "            elif len(trees[root])==2:\n",
    "                left,right = DFS(trees[root][0]), DFS(trees[root][1])\n",
    "                score = (n-left-right-1)*left*right if n-left-right-1>0 else left*right\n",
    "                below_cnt = left+right\n",
    "            \n",
    "            if score>max_score:\n",
    "                cnt  = 1\n",
    "                max_score = score \n",
    "            elif score==max_score:\n",
    "                cnt += 1\n",
    "            \n",
    "            return below_cnt+1 \n",
    "        \n",
    "        DFS(0)\n",
    "        return cnt \n",
    "            \n",
    "\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        graph = defaultdict(list)\n",
    "        for i, p in enumerate(parents[1:], 1):\n",
    "            graph[p].append(i)\n",
    "        max_score, ans = 0, 0\n",
    "\n",
    "        def f(x, fa):\n",
    "            nonlocal max_score, ans\n",
    "            left = f(graph[x][0], x) if graph[x] else 0\n",
    "            right = f(graph[x][1], x) if len(graph[x]) > 1 else 0\n",
    "            score = max(left, 1) * max(right, 1) * max(n - left - right - 1, 1)\n",
    "            if score > max_score:\n",
    "                max_score = score\n",
    "                ans = 1\n",
    "            elif score == max_score:\n",
    "                ans += 1\n",
    "            return left + right + 1\n",
    "        \n",
    "        f(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        \n",
    "        # Create a graph from the given parents list\n",
    "        graph = defaultdict(list)\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent != -1:\n",
    "                graph[parent].append(i)\n",
    "        \n",
    "        # Function to calculate the size of each subtree rooted at node\n",
    "        def dfs(node):\n",
    "            size = 1\n",
    "            for child in graph[node]:\n",
    "                size += dfs(child)\n",
    "            sizes[node] = size\n",
    "            return size\n",
    "        \n",
    "        # Calculate the size of each subtree\n",
    "        sizes = [0] * len(parents)\n",
    "        dfs(0)\n",
    "        \n",
    "        # Function to calculate the score of each node\n",
    "        def score(node):\n",
    "            total = 1\n",
    "            for child in graph[node]:\n",
    "                total *= (sizes[child])\n",
    "            if parents[node] != -1:\n",
    "                total *= (sizes[0] - sizes[node])\n",
    "            return total\n",
    "        \n",
    "        # Calculate the score of each node\n",
    "        scores = [score(i) for i in range(len(parents))]\n",
    "        \n",
    "        # Find the highest score and count the number of nodes with that score\n",
    "        highest_score = max(scores)\n",
    "        count = 0\n",
    "        for s in scores:\n",
    "            if s == highest_score:\n",
    "                count += 1\n",
    "                \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        \n",
    "        # Create a graph from the given parents list\n",
    "        graph = defaultdict(list)\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent != -1:\n",
    "                graph[parent].append(i)\n",
    "        \n",
    "        # Function to calculate the size of each subtree rooted at node\n",
    "        def dfs(node):\n",
    "            size = 1\n",
    "            for child in graph[node]:\n",
    "                size += dfs(child)\n",
    "            sizes[node] = size\n",
    "            return size\n",
    "        \n",
    "        # Calculate the size of each subtree\n",
    "        sizes = [0] * len(parents)\n",
    "        dfs(0)\n",
    "        \n",
    "        # Function to calculate the score of each node\n",
    "        def score(node):\n",
    "            total = 1\n",
    "            for child in graph[node]:\n",
    "                total *= (sizes[child])\n",
    "            if parents[node] != -1:\n",
    "                total *= (sizes[0] - sizes[node])\n",
    "            return total\n",
    "        \n",
    "        # Calculate the score of each node\n",
    "        scores = [score(i) for i in range(len(parents))]\n",
    "        \n",
    "        # Find the highest score and count the number of nodes with that score\n",
    "        highest_score = max(scores)\n",
    "        count = 0\n",
    "        for s in scores:\n",
    "            if s == highest_score:\n",
    "                count += 1\n",
    "                \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        \n",
    "        # Create a graph from the given parents list\n",
    "        graph = defaultdict(list)\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent != -1:\n",
    "                graph[parent].append(i)\n",
    "        \n",
    "        # Function to calculate the size of each subtree rooted at node\n",
    "        def dfs(node):\n",
    "            size = 1\n",
    "            for child in graph[node]:\n",
    "                size += dfs(child)\n",
    "            sizes[node] = size\n",
    "            return size\n",
    "        \n",
    "        # Calculate the size of each subtree\n",
    "        sizes = [0] * len(parents)\n",
    "        dfs(0)\n",
    "        \n",
    "        # Function to calculate the score of each node\n",
    "        def score(node):\n",
    "            total = 1\n",
    "            for child in graph[node]:\n",
    "                total *= (sizes[child])\n",
    "            if parents[node] != -1:\n",
    "                total *= (sizes[0] - sizes[node])\n",
    "            return total\n",
    "        \n",
    "        # Calculate the score of each node\n",
    "        scores = [score(i) for i in range(len(parents))]\n",
    "        \n",
    "        # Find the highest score and count the number of nodes with that score\n",
    "        highest_score = max(scores)\n",
    "        count = 0\n",
    "        for s in scores:\n",
    "            if s == highest_score:\n",
    "                count += 1\n",
    "                \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        \n",
    "        # Create a graph from the given parents list\n",
    "        graph = defaultdict(list)\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent != -1:\n",
    "                graph[parent].append(i)\n",
    "        \n",
    "        # Function to calculate the size of each subtree rooted at node\n",
    "        def dfs(node):\n",
    "            size = 1\n",
    "            for child in graph[node]:\n",
    "                size += dfs(child)\n",
    "            sizes[node] = size\n",
    "            return size\n",
    "        \n",
    "        # Calculate the size of each subtree\n",
    "        sizes = [0] * len(parents)\n",
    "        dfs(0)\n",
    "        \n",
    "        # Function to calculate the score of each node\n",
    "        def score(node):\n",
    "            total = 1\n",
    "            for child in graph[node]:\n",
    "                total *= (sizes[child])\n",
    "            if parents[node] != -1:\n",
    "                total *= (sizes[0] - sizes[node])\n",
    "            return total\n",
    "        \n",
    "        # Calculate the score of each node\n",
    "        scores = [score(i) for i in range(len(parents))]\n",
    "        \n",
    "        # Find the highest score and count the number of nodes with that score\n",
    "        highest_score = max(scores)\n",
    "        count = 0\n",
    "        for s in scores:\n",
    "            if s == highest_score:\n",
    "                count += 1\n",
    "                \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        \n",
    "        # Create a graph from the given parents list\n",
    "        graph = defaultdict(list)\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent != -1:\n",
    "                graph[parent].append(i)\n",
    "        \n",
    "        # Function to calculate the size of each subtree rooted at node\n",
    "        def dfs(node):\n",
    "            size = 1\n",
    "            for child in graph[node]:\n",
    "                size += dfs(child)\n",
    "            sizes[node] = size\n",
    "            return size\n",
    "        \n",
    "        # Calculate the size of each subtree\n",
    "        sizes = [0] * len(parents)\n",
    "        dfs(0)\n",
    "        \n",
    "        # Function to calculate the score of each node\n",
    "        def score(node):\n",
    "            total = 1\n",
    "            for child in graph[node]:\n",
    "                total *= (sizes[child])\n",
    "            if node != 0:\n",
    "                total *= (sizes[0] - sizes[node])\n",
    "            return total\n",
    "        \n",
    "        # Calculate the score of each node\n",
    "        scores = [score(i) for i in range(len(parents))]\n",
    "        \n",
    "        # Find the highest score and count the number of nodes with that score\n",
    "        highest_score = max(scores)\n",
    "        count = 0\n",
    "        for s in scores:\n",
    "            if s == highest_score:\n",
    "                count += 1\n",
    "                \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes1(self, parents: List[int]) -> int:\n",
    "        n=len(parents)\n",
    "        root=collections.defaultdict(list)\n",
    "        for i in range(1,n):\n",
    "            root[parents[i]].append(i)\n",
    "\n",
    "        def dfs(curid):\n",
    "            cnt=0\n",
    "            for child in root[curid]:\n",
    "                cnt += dfs(child)\n",
    "            return cnt+1\n",
    "\n",
    "        maxscore=-1\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            left=0\n",
    "            right=0\n",
    "            l=len(root[i])\n",
    "            if l==1:\n",
    "                left=dfs(root[i][0])\n",
    "            elif l==2:\n",
    "                left=dfs(root[i][0])\n",
    "                right=dfs(root[i][1])\n",
    "            par=n-left-right-1\n",
    "            if par==0:\n",
    "                if left==0 and right==0:\n",
    "                    tmp=0\n",
    "                elif left==0:\n",
    "                    tmp=right\n",
    "                elif right==0:\n",
    "                    tmp=left\n",
    "                else:\n",
    "                    tmp=left*right\n",
    "            else:\n",
    "                if left==0 and right==0:\n",
    "                    tmp=par\n",
    "                elif left==0:\n",
    "                    tmp=right*par\n",
    "                elif right==0:\n",
    "                    tmp=left*par\n",
    "                else:\n",
    "                    tmp=left*right*par\n",
    "            if maxscore<tmp:\n",
    "                maxscore=tmp\n",
    "                res=1\n",
    "            elif maxscore==tmp:\n",
    "                res+=1\n",
    "        return res\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n=len(parents)\n",
    "        root=collections.defaultdict(list)\n",
    "        for i in range(1,n):\n",
    "            root[parents[i]].append(i)\n",
    "        maxscore=0\n",
    "        cnt=0\n",
    "        def dfs(node:int):\n",
    "            score=1\n",
    "            size=n-1\n",
    "            for ch in root[node]:\n",
    "                sz=dfs(ch)\n",
    "                score*=sz\n",
    "                size-=sz\n",
    "            if node!=0:\n",
    "                score*=size\n",
    "            nonlocal maxscore, cnt\n",
    "            if score==maxscore:\n",
    "                cnt+=1\n",
    "            elif score>maxscore:\n",
    "                maxscore=score\n",
    "                cnt=1\n",
    "            return n-size\n",
    "        dfs(0)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        # def traverse(tree, cur):\n",
    "        #     count = 1\n",
    "        #     for i in tree[cur]:\n",
    "        #         count += traverse(tree, i)\n",
    "        #     tree_node[cur] = count\n",
    "        #     return count \n",
    "\n",
    "        # tree = defaultdict(list)\n",
    "        # for i, x in enumerate(parents):\n",
    "        #     if i == 0:\n",
    "        #         continue\n",
    "        #     tree[x].append(i)\n",
    "        # tree_node = {}\n",
    "        # traverse(tree, 0)\n",
    "        # max_val = count = 0\n",
    "        # n = len(parents)\n",
    "        # for i in range(n):\n",
    "        #     mul = cnt = 1\n",
    "        #     for j in tree[i]:\n",
    "        #         mul *= tree_node[j]\n",
    "        #         cnt += tree_node[j]\n",
    "        #     if cnt < n:\n",
    "        #         mul *= (n-cnt)\n",
    "        #     if mul > max_val:\n",
    "        #         max_val = mul\n",
    "        #         count = 1\n",
    "        #     elif mul == max_val:\n",
    "        #         count += 1\n",
    "        # return count\n",
    "\n",
    "        # ----------------------\n",
    "        def traverse(cur):\n",
    "            nonlocal max_val, res, n\n",
    "            mul = count = 1\n",
    "            for i in tree[cur]:\n",
    "                temp = traverse(i)\n",
    "                count += temp\n",
    "                mul *= max(temp, 1)\n",
    "            if count < n:\n",
    "                mul *= (n-count)\n",
    "            if mul > max_val:\n",
    "                max_val, res = mul, 1\n",
    "            elif mul == max_val:\n",
    "                res += 1\n",
    "            return count \n",
    "\n",
    "        tree = defaultdict(list)\n",
    "        for i, x in enumerate(parents[1:], 1):\n",
    "            tree[x].append(i)\n",
    "        max_val = res = 0\n",
    "        n = len(parents)\n",
    "        traverse(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        def dfs(node):\n",
    "            nonlocal parents, sub_node_cnt, visited\n",
    "            local_sub_node_cnt = 0\n",
    "            for next_node in node_to_next_node[node]:\n",
    "                if not visited[next_node]:\n",
    "                    visited[next_node] = True\n",
    "                    dfs(next_node)\n",
    "\n",
    "                local_sub_node_cnt += sub_node_cnt[next_node] + 1\n",
    "            sub_node_cnt[node] = local_sub_node_cnt\n",
    "\n",
    "        sub_node_cnt = [0 for _ in range(len(parents))]\n",
    "        visited = [False] * len(parents)\n",
    "        node_to_next_node = collections.defaultdict(list)\n",
    "        for idx, item in enumerate(parents):\n",
    "            node_to_next_node[item].append(idx)\n",
    "        dfs(0)\n",
    "\n",
    "        res, res_cnt = float(\"-inf\"), 0\n",
    "        for i in range(len(parents)):\n",
    "            tmp = 1\n",
    "\n",
    "            # 如果删除 第 i 个节点\n",
    "            if len(node_to_next_node[i]) == 0:\n",
    "                # 叶子节点\n",
    "                tmp = len(parents) - 1\n",
    "            elif len(node_to_next_node[i]) == 1:\n",
    "                # 仅存在 左子树 或 右子树\n",
    "                x1 = sub_node_cnt[i]\n",
    "                if len(parents) - 1 - x1 != 0:\n",
    "                    tmp = (len(parents) - 1 - x1)  * x1\n",
    "                else:\n",
    "                    tmp = x1\n",
    "            else:\n",
    "                # 左右子树都存在\n",
    "                x1 = sub_node_cnt[node_to_next_node[i][0]] + 1\n",
    "                x2 = sub_node_cnt[node_to_next_node[i][1]] + 1\n",
    "                if len(parents) - 1 - x1 - x2 != 0:\n",
    "                    tmp = x1 * x2 * (len(parents) - 1 - x1 - x2)\n",
    "                else:\n",
    "                    tmp = x1 * x2\n",
    "\n",
    "            # print(i, tmp, node_to_next_node[i], sub_node_cnt[i])\n",
    "\n",
    "            if tmp > res:\n",
    "                res = tmp\n",
    "                res_cnt = 1\n",
    "            elif tmp == res:\n",
    "                res_cnt += 1\n",
    "            \n",
    "        return res_cnt\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        def dfs(node):\n",
    "            nonlocal parents, sub_node_cnt, visited\n",
    "            local_sub_node_cnt = 0\n",
    "            for next_node in node_to_next_node[node]:\n",
    "                if not visited[next_node]:\n",
    "                    visited[next_node] = True\n",
    "                    dfs(next_node)\n",
    "\n",
    "                local_sub_node_cnt += sub_node_cnt[next_node] + 1\n",
    "            sub_node_cnt[node] = local_sub_node_cnt\n",
    "\n",
    "        sub_node_cnt = [0 for _ in range(len(parents))]\n",
    "        visited = [False] * len(parents)\n",
    "        node_to_next_node = collections.defaultdict(list)\n",
    "        for idx, item in enumerate(parents):\n",
    "            node_to_next_node[item].append(idx)\n",
    "        dfs(0)\n",
    "\n",
    "        res, res_cnt = float(\"-inf\"), 0\n",
    "        for i in range(len(parents)):\n",
    "            tmp = 1\n",
    "\n",
    "            # 如果删除 第 i 个节点\n",
    "            if len(node_to_next_node[i]) == 0:\n",
    "                # 叶子节点\n",
    "                tmp = len(parents) - 1\n",
    "            elif len(node_to_next_node[i]) == 1:\n",
    "                # 仅存在 左子树 或 右子树\n",
    "                x1 = sub_node_cnt[i]\n",
    "                if len(parents) - 1 - x1 != 0:\n",
    "                    tmp = (len(parents) - 1 - x1)  * x1\n",
    "                else:\n",
    "                    tmp = x1\n",
    "            else:\n",
    "                # 左右子树都存在\n",
    "                x1 = sub_node_cnt[node_to_next_node[i][0]] + 1\n",
    "                x2 = sub_node_cnt[node_to_next_node[i][1]] + 1\n",
    "                if len(parents) - 1 - x1 - x2 != 0:\n",
    "                    tmp = x1 * x2 * (len(parents) - 1 - x1 - x2)\n",
    "                else:\n",
    "                    tmp = x1 * x2\n",
    "\n",
    "            # print(i, tmp, node_to_next_node[i], sub_node_cnt[i])\n",
    "\n",
    "            if tmp > res:\n",
    "                res = tmp\n",
    "                res_cnt = 1\n",
    "            elif tmp == res:\n",
    "                res_cnt += 1\n",
    "            \n",
    "        return res_cnt\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
